package leetcode每日一题.leetcode20212;


/**
 * 1. 问题描述
 *      判断托普利兹矩阵
 *
 * 2. 算法分析
 *      暴力扫描完事,找元素之间的规律即可  时间复杂度为O(m*n)
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q022_托普利兹矩阵的判断 {

    // 任意对角线的元素相同
    // 假设当前矩阵为m * n的规模，则该矩有多少对角线呢? 有 m + n
    // 暴力扫描每一个对角线
    // 上对角0,1,2,...,n  n为列数
    // 下对角1,2,...,m m为行数
    public boolean isToeplitzMatrix1(int[][] matrix) {
        int row = matrix.length; // 行数
        int col = matrix[0].length; // 列数
        boolean isTrue = true; // 设置判断是否为托普利兹矩阵的布尔变量
        // 判断所有上对角
        for(int j = 0; j < col; j++) { // 扫描上对角编号
            // 判断当前对角,当前起始元素为 matrix[0][j]
            int x = 0;
            int y = j;
            while(x < row - 1 && y < col - 1) {
                if(matrix[x][y] != matrix[x+1][y+1]) {
                    isTrue = false;
                    break;
                }
                x++;
                y++;
            }
        }

        // 判断所有下对角
        for(int i = 1; i < row; i++) { // 扫描下对角编号
            // 判断当前对角 起始元素matrix[i][0]
            int x = i;
            int y = 0;
            while(x < row - 1 && y < col - 1) {
                if(matrix[x][y] != matrix[x+1][y+1]) {
                    isTrue = false;
                    break;
                }
                x++;
                y++;
            }
        }

        return isTrue;
    }

    // 上述代码的简化版本
    public boolean isToeplitzMatrix2(int[][] matrix) {
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i-1][j-1] != matrix[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}
